package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-07 18:43
 * @description: Functions of this class is
 **/
public class 保持城市天际线 {
    public static void main(String args[]){
        int grid[][] = new int[][]{ {3,0,8,4},
                                    {2,4,5,7},
                                    {9,2,6,3},
                                    {0,3,1,0}};
        System.out.println(maxIncreaseKeepingSkyline(grid));
    }
    public static int maxIncreaseKeepingSkyline(int[][] grid) {
        int L[]=new int[grid[0].length];//开一个数组表示每一行的最高高度,即水平方向上看
        int H[]=new int[grid.length];//开一个数组表示每一列的最长宽度,即竖直方向上看

        for(int i=0;i<grid[0].length;i++){
            int maxL=Integer.MIN_VALUE;//定义一个变量存储当前行的最大值
            for(int j=0;j<grid.length;j++){
                //从每一行逐行遍历找到当前行最大的
                if(grid[i][j]>maxL){
                    maxL=grid[i][j];
                }
            }
            L[i]=maxL;//没扫描完一行后记录最大值
        }
        int j;
        for(int i=0;i<grid[0].length;i++){
            int maxH=Integer.MIN_VALUE;//定义一个变量存储当前列的最大值
            for(j=0;j<grid.length;j++){
                //从每一行逐行遍历找到当前列最大的
                if(grid[j][i]>maxH){
                    maxH=grid[j][i];
                }
            }
            H[i]=maxH;//没扫描完一列后记录最大值
        }

        int tot=0;
        //开始进行天际线增加数量的记录*
        for(int i=0;i<L.length;i++) {
            for (j = 0; j <H.length; j++) {
                //贪心思想，每栋建筑所能增加到的最高高度既为当前建筑所在行的最大值与所在列的最大值中两者的最小值，这样便能满足题意
                tot+=(Math.min(L[i],H[j])-grid[i][j]);//所以天际线增加的和即为，当前建筑所在行与所在列的最大高度的最小值与该建筑之前高度的差
            }
        }
        return tot;
    }
}